//
// Created by Administrator on 2021/6/30.
//
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
private:
    const vector<vector<int>> move{{1,  0},
                                   {-1, 0},
                                   {0,  1},
                                   {0,  -1}};
public:
    vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int newColor) {
        /**
         * 把与初始点连通且值相等的所有点都改为新值
         */
        auto m = image.size(), n = image[0].size();
        // 初始点的值
        int targetValue = image[sr][sc];
        // 队列,放入初始坐标
        queue<pair<int, int>> q;
        q.emplace(sr, sc);
        // 记录经过的点
        unordered_set<int> seen;
        seen.insert(sr*n+sc);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            // 上色
            image[p.first][p.second] = newColor;
            for (int i = 0; i < 4; ++i) {
                // 相邻的格子
                int nextX = p.first + move[i][0];
                int nextY = p.second + move[i][1];
                int globalIndex = nextX * n + nextY;
                if (nextX < 0 or nextX >= m or nextY < 0 or nextY >= n or seen.count(globalIndex))
                    continue;
                if (image[nextX][nextY] == targetValue) {
                    q.emplace(nextX, nextY);
                    seen.insert(globalIndex);
                }

            }
        }
        return image;
    }
};

int main() {
    vector<vector<int>> image{{0, 0, 0},
                              {0, 0, 0}};
    Solution sol;
    auto ans = sol.floodFill(image, 0, 0, 2);
    for (auto &x:ans) {
        for (auto &y:x) {
            cout << y << endl;
        }
    }
    return 0;
}